package leetcode.code787.CheapestFlightsWithinKStops;

import java.util.HashMap;
import java.util.Map;

/**
 * dp超时
 * @author Max
 * @date 2021年8月24日
 * @description
 */
public class Solution78702 extends CheapestFlightsWithinKStops {

	@Override
	public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
		Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
		for (int[] flight : flights) {
			if (map.containsKey(flight[0])) {
				Map<Integer, Integer> temp = map.get(flight[0]);
				temp.put(flight[1], flight[2]);
			} else {
				Map<Integer, Integer> temp = new HashMap<>();
				temp.put(flight[1], flight[2]);
				map.put(flight[0], temp);
			}
		}
		Integer[][][] cache = new Integer[n][n][k + 1];
		final int MAX = 1000001;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int m = 0; m <= k; m++) {
					if (m == 0) {
						if (map.containsKey(i) && map.get(i).containsKey(j)) {
							cache[i][j][m] = map.get(i).get(j);
						} else {
							cache[i][j][m] = null;
						}
					} else if (i == j) {
						cache[i][j][m] = -1;//?
					} else {
						cache[i][j][m] = -1;
					}
				}
			}
		}
		if (k == 0) {
			return cache[src][dst][0] == null ? -1 : cache[src][dst][0];//return cache[src][dst][0]; 就错了 这个tm可能null啊
		}
		for (int m = 1; m <= k; m++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					Integer temp = null;//默认是null不可抵达，不然有问题
					for (int p = 0; p < n; p++) {
						for (int q = 0; q <= k && m - q - 1 >= 0; q++) {
							Integer step1 = cache[i][p][q];
							Integer step2 = cache[p][j][m - q - 1];
							if (step1 != null && step2 != null) {
								int now = cache[i][p][q] + cache[p][j][m - q - 1];
								if (temp == null)
									temp = MAX;
								temp = Math.min(now, temp);
							}
						}
					}
					cache[i][j][m] = temp;
				}
			}
		}
		Integer min = null;
		for (int i = 0; i <= k; i++) {
			if (cache[src][dst][i] != null && cache[src][dst][i] != -1) {
				if (min == null)
					min = MAX;
				min = Math.min(min, cache[src][dst][i]);
			}
		}
		return min == null ? -1 : min;
	}

	public static void main(String[] args) {
		Solution78702 so = new Solution78702();
//		so.debug1();
//		so.debug2();
//		so.debug3();
//		so.debug4();
//		so.debug5();
		so.debug6();
	}

}
